package 链表题目;

import 链表题目.model.ListNode;

// 相交链表
// https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
// 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
public class 相交链表 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
/*        HashSet<ListNode> listNodes = new HashSet<>();
        while (headA != null) {
            listNodes.add(headA);
            headA = headA.next;
        }
        while (headB != null) {
            if (listNodes.contains(headB)) {
                return headB;
            }else {
                headB = headB.next;
            }
        }
        return null;*/
        // 最优解
        // 两个链表长度不相等情况下:
        //      双指针遍历两个链表，它们如果有交点一定会在交点相遇
        //      如果没有交点，那么它们两个会同时等于null跳出循环
        // 想等情况下：
        //      直接交点处相遇，如果没焦点同时遍历到链表尾部返回！
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}
